#include <iostream>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	int sumRootToLeaf(TreeNode* root) {
		if (!root) return 0;
		return dfs(root, 0);
	}

private:
	//int dfs(TreeNode* root, int sum) {
	//    if (!root) return 0;
	//    sum = 2 * sum + root->val;

	//    if (!root->left && !root->right) {
	//        return sum;
	//    }
	//    else {
	//        return dfs(root->left, sum) + dfs(root->right, sum);
	//    }
	//}

	int dfs(TreeNode* root, int sum) {
		if (!root) return 0;
		sum = 2 * sum + root->val;
		if (!root->left && !root->right) {
			return sum;
		}
		else {
			return dfs(root->left, sum) + dfs(root->right, sum);
		}
	}
};

int main()
{
	Solution s;

	{
		TreeNode nodes[7];

		for (int i = 0; i < 3; ++i) {
			nodes[i].left = &nodes[2 * i + 1];
			nodes[i].right = &nodes[2 * i + 2];
		}
		nodes[0].val = 1;
		nodes[2].val = 1;
		nodes[4].val = 1;
		nodes[6].val = 1;

		int res = s.sumRootToLeaf(&nodes[0]);
		printf("%d\n", res);
	}

	return 0;
}